package com.yanceysong.codetop.s1_s10;

import java.util.HashMap;

/**
 * @ClassName S2_Mid_3_无重复最长子串
 * @Description
 * @date 2024/6/4 下午1:19
 * @Author yanceysong
 * @Version 1.0
 */
public class S1_Mid_3_无重复字符的最长子串 {
    /**
     * LeetCode：
     * <a href="https://leetcode.cn/problems/longest-substring-without-repeating-characters/">...</a>
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度
     * 示例 1:
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * <p>
     * 使用滑动窗口法求解无重复字符的最长子串长度
     * <p>
     * 算法原理：
     * 1. 使用HashMap记录每个字符最后出现的位置
     * 2. 使用双指针维护一个滑动窗口，窗口内的字符都是唯一的
     * 3. 当遇到重复字符时，移动左指针到重复字符的下一个位置
     * 4. 持续更新窗口的最大长度
     * <p>
     * 核心思想：
     * - 右指针不断向右移动扩展窗口
     * - 当发现重复字符时，左指针跳跃到合适位置收缩窗口
     * - 窗口内始终保持字符的唯一性
     * - 记录过程中窗口的最大长度
     * <p>
     * 图解示例：s = "abcabcbb"
     * <p>
     * 字符串可视化：
     * 索引: 0 1 2 3 4 5 6 7
     * 字符: a b c a b c b b
     * <p>
     * 滑动窗口移动过程：
     * <p>
     * 初始状态：
     * HashMap: {}
     * leftBoundary = 0, currentMaxLength = 0
     * <p>
     * 步骤1: rightPointer=0, 字符='a'
     * HashMap中没有'a'，添加 {'a': 0}
     * 窗口: [a] (索引0-0)
     * currentMaxLength = max(0, 0-0+1) = 1
     * <p>
     * 步骤2: rightPointer=1, 字符='b'
     * HashMap中没有'b'，添加 {'a': 0, 'b': 1}
     * 窗口: [a,b] (索引0-1)
     * currentMaxLength = max(1, 1-0+1) = 2
     * <p>
     * 步骤3: rightPointer=2, 字符='c'
     * HashMap中没有'c'，添加 {'a': 0, 'b': 1, 'c': 2}
     * 窗口: [a,b,c] (索引0-2)
     * currentMaxLength = max(2, 2-0+1) = 3
     * <p>
     * 步骤4: rightPointer=3, 字符='a' (重复！)
     * HashMap中有'a'，位置为0
     * leftBoundary = max(0, 0+1) = 1
     * 更新 {'a': 3, 'b': 1, 'c': 2}
     * 窗口: [b,c,a] (索引1-3)
     * currentMaxLength = max(3, 3-1+1) = 3
     * <p>
     * 步骤5: rightPointer=4, 字符='b' (重复！)
     * HashMap中有'b'，位置为1
     * leftBoundary = max(1, 1+1) = 2
     * 更新 {'a': 3, 'b': 4, 'c': 2}
     * 窗口: [c,a,b] (索引2-4)
     * currentMaxLength = max(3, 4-2+1) = 3
     * <p>
     * 步骤6: rightPointer=5, 字符='c' (重复！)
     * HashMap中有'c'，位置为2
     * leftBoundary = max(2, 2+1) = 3
     * 更新 {'a': 3, 'b': 4, 'c': 5}
     * 窗口: [a,b,c] (索引3-5)
     * currentMaxLength = max(3, 5-3+1) = 3
     * <p>
     * 步骤7: rightPointer=6, 字符='b' (重复！)
     * HashMap中有'b'，位置为4
     * leftBoundary = max(3, 4+1) = 5
     * 更新 {'a': 3, 'b': 6, 'c': 5}
     * 窗口: [c,b] (索引5-6)
     * currentMaxLength = max(3, 6-5+1) = 3
     * <p>
     * 步骤8: rightPointer=7, 字符='b' (重复！)
     * HashMap中有'b'，位置为6
     * leftBoundary = max(5, 6+1) = 7
     * 更新 {'a': 3, 'b': 7, 'c': 5}
     * 窗口: [b] (索引7-7)
     * currentMaxLength = max(3, 7-7+1) = 3
     * <p>
     * 最终结果：最长无重复子串长度 = 3
     * 对应子串："abc" (可能有多个长度相同的子串)
     * <p>
     * 关键算法细节：abba问题的解决
     * 考虑字符串 "abba"：
     * 步骤1-3: 处理 "abb" -> leftBoundary=0, window=[a,b,b] 但第二个'b'会导致leftBoundary=2
     * 步骤4: 处理最后的'a' -> HashMap中'a'的位置是0
     * 如果简单设置 leftBoundary = 0+1 = 1，会导致窗口退回到之前的状态
     * 使用 Math.max(leftBoundary, 旧位置+1) 确保左边界只向前移动，不后退
     * <p>
     * 可视化窗口移动：
     * .s = "a b c a b c b b"
     * .↑       ↑
     * .left   right   窗口: "abc" 长度=3
     * <p>
     * .s = "a b c a b c b b"
     * .↑     ↑
     * .left right   窗口: "cab" 长度=3
     * <p>
     * .s = "a b c a b c b b"
     * .↑   ↑
     * .left right 窗口: "abc" 长度=3
     * <p>
     * 时间复杂度：O(n)，每个字符最多被访问两次（一次加入窗口，一次移出窗口）
     * 空间复杂度：O(min(m,n))，其中m是字符集大小，n是字符串长度
     */
    public int lengthOfLongestSubstring(String s) {
        // 边界条件检查
        if (s == null || s.isEmpty()) {
            return 0;
        }

        // 使用HashMap记录每个字符最后出现的位置（索引）
        HashMap<Character, Integer> characterPositionMap = new HashMap<>();

        // 记录当前找到的最长无重复子串的长度
        int currentMaxLength = 0;

        // 滑动窗口的左边界（左指针）
        int leftBoundary = 0;

        // 滑动窗口的右边界（右指针），通过for循环移动
        for (int rightPointer = 0; rightPointer < s.length(); rightPointer++) {
            // 获取当前字符
            char currentCharacter = s.charAt(rightPointer);

            // 检查当前字符是否在窗口中已经存在（即是否重复）
            if (characterPositionMap.containsKey(currentCharacter)) {
                // 发现重复字符，需要移动左边界
                // 使用Math.max确保左边界只向前移动，不后退（解决abba问题）
                // 移动到重复字符上次出现位置的下一个位置
                leftBoundary = Math.max(leftBoundary, characterPositionMap.get(currentCharacter) + 1);
            }

            // 更新当前字符在HashMap中的位置（无论是否重复都要更新）
            characterPositionMap.put(currentCharacter, rightPointer);

            // 计算当前窗口的长度，并更新最大长度
            // 当前窗口长度 = rightPointer - leftBoundary + 1
            int currentWindowLength = rightPointer - leftBoundary + 1;
            currentMaxLength = Math.max(currentMaxLength, currentWindowLength);
        }

        return currentMaxLength;
    }

    public static void main(String[] args) {
        S1_Mid_3_无重复字符的最长子串 solution = new S1_Mid_3_无重复字符的最长子串();

        System.out.println("=== 无重复最长子串测试开始 ===");

        // 测试1: 基本功能测试 - 题目示例
        System.out.println("\n--- 测试1: 基本功能测试 (题目示例) ---");
        testBasicExamples(solution);

        // 测试2: 边界情况测试
        System.out.println("\n--- 测试2: 边界情况测试 ---");
        testBoundaryCases(solution);

        // 测试3: 特殊字符测试
        System.out.println("\n--- 测试3: 特殊字符测试 ---");
        testSpecialCharacters(solution);

        // 测试4: 复杂重复模式测试
        System.out.println("\n--- 测试4: 复杂重复模式测试 ---");
        testComplexPatterns(solution);

        // 测试5: 性能测试
        System.out.println("\n--- 测试5: 性能测试 ---");
        testPerformance(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试基本功能 - 题目给出的示例
     */
    private static void testBasicExamples(S1_Mid_3_无重复字符的最长子串 solution) {
        // 示例1: "abcabcbb" -> 3 ("abc")
        String s1 = "abcabcbb";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 3, 子串: \"abc\")");
        assert result1 == 3 : "abcabcbb的最长无重复子串长度应该是3";

        // 示例2: "bbbbb" -> 1 ("b")
        String s2 = "bbbbb";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 1, 子串: \"b\")");
        assert result2 == 1 : "bbbbb的最长无重复子串长度应该是1";

        // 示例3: "pwwkew" -> 3 ("wke")
        String s3 = "pwwkew";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 3, 子串: \"wke\")");
        assert result3 == 3 : "pwwkew的最长无重复子串长度应该是3";

        // 示例4: "abba" -> 2 ("ab" 或 "ba")
        String s4 = "abba";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 2, 子串: \"ab\" 或 \"ba\")");
        assert result4 == 2 : "abba的最长无重复子串长度应该是2";

        System.out.println("✓ 基本功能测试通过");
    }

    /**
     * 测试边界情况
     */
    private static void testBoundaryCase(S1_Mid_3_无重复字符的最长子串 solution) {
        // 空字符串
        String s1 = "";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 0)");
        assert result1 == 0 : "空字符串的最长无重复子串长度应该是0";

        // 单个字符
        String s2 = "a";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 1)");
        assert result2 == 1 : "单个字符的最长无重复子串长度应该是1";

        // 两个相同字符
        String s3 = "aa";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 1)");
        assert result3 == 1 : "两个相同字符的最长无重复子串长度应该是1";

        // 两个不同字符
        String s4 = "ab";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 2)");
        assert result4 == 2 : "两个不同字符的最长无重复子串长度应该是2";

        // 全部字符都不重复
        String s5 = "abcdefg";
        int result5 = solution.lengthOfLongestSubstring(s5);
        System.out.println("输入: \"" + s5 + "\" -> 输出: " + result5 + " (期望: 7)");
        assert result5 == 7 : "全部不重复字符的最长无重复子串长度应该等于字符串长度";

        System.out.println("✓ 边界情况测试通过");
    }

    /**
     * 修正方法名并实现边界情况测试
     */
    private static void testBoundaryCases(S1_Mid_3_无重复字符的最长子串 solution) {
        testBoundaryCase(solution);
    }

    /**
     * 测试特殊字符
     */
    private static void testSpecialCharacters(S1_Mid_3_无重复字符的最长子串 solution) {
        // 包含空格
        String s1 = "a b c a";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 3, 子串: \"a b\" 或 \"b c\")");
        assert result1 == 3 : "包含空格的字符串测试失败";

        // 包含数字
        String s2 = "123321";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 3, 子串: \"123\" 或 \"321\")");
        assert result2 == 3 : "包含数字的字符串测试失败";

        // 包含特殊符号
        String s3 = "!@#$%!";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 5, 子串: \"!@#$%\")");
        assert result3 == 5 : "包含特殊符号的字符串测试失败";

        // 混合字符
        String s4 = "a1!b2@a";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 6, 子串: \"1!b2@a\")");
        assert result4 == 6 : "混合字符的字符串测试失败";

        System.out.println("✓ 特殊字符测试通过");
    }

    /**
     * 测试复杂重复模式
     */
    private static void testComplexPatterns(S1_Mid_3_无重复字符的最长子串 solution) {
        // 测试abba模式（代码注释中的特殊情况）
        String s1 = "abba";
        int result1 = solution.lengthOfLongestSubstring(s1);
        System.out.println("输入: \"" + s1 + "\" -> 输出: " + result1 + " (期望: 2, 验证abba特殊情况)");
        assert result1 == 2 : "abba模式测试失败";

        // 测试更复杂的abba模式
        String s2 = "abcba";
        int result2 = solution.lengthOfLongestSubstring(s2);
        System.out.println("输入: \"" + s2 + "\" -> 输出: " + result2 + " (期望: 3, 子串: \"abc\" 或 \"cba\")");
        assert result2 == 3 : "abcba模式测试失败";

        // 测试回文模式
        String s3 = "abccba";
        int result3 = solution.lengthOfLongestSubstring(s3);
        System.out.println("输入: \"" + s3 + "\" -> 输出: " + result3 + " (期望: 3, 子串: \"abc\" 或 \"cba\")");
        assert result3 == 3 : "回文模式测试失败";

        // 测试长距离重复
        String s4 = "abcdefga";
        int result4 = solution.lengthOfLongestSubstring(s4);
        System.out.println("输入: \"" + s4 + "\" -> 输出: " + result4 + " (期望: 7, 子串: \"bcdefga\")");
        assert result4 == 7 : "长距离重复测试失败";

        // 测试多个重复点
        String s5 = "abcabcabcabc";
        int result5 = solution.lengthOfLongestSubstring(s5);
        System.out.println("输入: \"" + s5 + "\" -> 输出: " + result5 + " (期望: 3, 子串: \"abc\")");
        assert result5 == 3 : "多个重复点测试失败";

        // 测试交替模式
        String s6 = "ababab";
        int result6 = solution.lengthOfLongestSubstring(s6);
        System.out.println("输入: \"" + s6 + "\" -> 输出: " + result6 + " (期望: 2, 子串: \"ab\")");
        assert result6 == 2 : "交替模式测试失败";

        System.out.println("✓ 复杂重复模式测试通过");
    }

    /**
     * 测试性能
     */
    private static void testPerformance(S1_Mid_3_无重复字符的最长子串 solution) {
        // 构造较长的字符串进行性能测试
        StringBuilder sb = new StringBuilder();

        // 测试1: 长字符串，无重复
        for (int i = 0; i < 1000; i++) {
            sb.append((char) ('a' + (i % 26)));
        }
        String longString1 = sb.toString();

        long startTime = System.currentTimeMillis();
        int result1 = solution.lengthOfLongestSubstring(longString1);
        long endTime = System.currentTimeMillis();

        System.out.println("长字符串测试1 (1000字符，循环字母): " + result1 + " (期望: 26)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result1 == 26 : "长字符串性能测试1失败";

        // 测试2: 长字符串，全部相同
        String longString2 = "a".repeat(1000);

        startTime = System.currentTimeMillis();
        int result2 = solution.lengthOfLongestSubstring(longString2);
        endTime = System.currentTimeMillis();

        System.out.println("长字符串测试2 (1000个相同字符): " + result2 + " (期望: 1)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result2 == 1 : "长字符串性能测试2失败";

        // 测试3: 长字符串，最坏情况（每两个字符重复）
        sb = new StringBuilder();
        sb.append("ab".repeat(500));
        String longString3 = sb.toString();

        startTime = System.currentTimeMillis();
        int result3 = solution.lengthOfLongestSubstring(longString3);
        endTime = System.currentTimeMillis();

        System.out.println("长字符串测试3 (1000字符，ab重复): " + result3 + " (期望: 2)");
        System.out.println("执行时间: " + (endTime - startTime) + "ms");
        assert result3 == 2 : "长字符串性能测试3失败";

        System.out.println("✓ 性能测试通过");
    }


}
